#include<vector>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right)
    {
    }
};

class Solution
{
public:
    std::vector<std::vector<int>> res;
    std::vector<TreeNode*> mid;

    std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        if (root == nullptr) return {};
        int l, r;
        r = 0;
        l = 0;
        mid.push_back(root);
        r++;
        int floor = 0;
        res.push_back({});
        while (l != r)
        {
            int size = r - l;
            res.push_back({});
            int nowl = l;
            int nowr = r;
            while (size-- > 0)
            {
                if (mid[l]->left == nullptr)
                {
                }
                else
                {
                    mid.push_back(mid[l]->left);
                    r++;
                }
                if (mid[l]->right == nullptr)
                {
                }
                else
                {
                    mid.push_back(mid[l]->right);
                    r++;
                }
                l++;
            }

            if (floor % 2 == 0)
            {
                for (int i = nowl; i < nowr; i++)
                {
                    res[floor].push_back(mid[i]->val);
                }
            }
            else
            {
                for (int i = nowr - 1; i >= nowl; i--)
                {
                    res[floor].push_back(mid[i]->val);
                }
            }


            floor++;
        }
        int a = res[floor].size();
        res.pop_back();
        return res;
    }
};

